\documentclass[../libro.tex]{subfiles}

\begin{document}

\ifSubfilesClassLoaded{\appendix}{}

\chapter{求和号与数学归纳法}

我在这儿简要地介绍求和号与数学归纳法.

\clearpage

\section{求和号}

为简便地表示求和,
人们聪明地作了\emph{求和号} \(\sum\).
对应拉丁字母 S, \(\sum\) 来自 \angla{sum} (英语).

设 \(a_m\), \(a_{m+1}\), \(\dots\), \(a_n\) 是
\(n - m + 1\)~个数 (\(n \geq m\)).
我们可简单地写这 \(n - m + 1\)~个数的和
\begin{equation}
    a_m + a_{m+1} + \dots + a_n
    \label{eq:B0101}
\end{equation}
为
\begin{equation}
    \sum_{i = m}^{n} {a_i}.
    \label{eq:B0102}
\end{equation}
比如,
\begin{align*}
     & 6 + 5x + 4x^2 + 3x^3 + 2x^4 + x^5
    = \sum_{i = 0}^{5} {(6 - i)x^i};                       \\
     & 1 + 2 + \dots + (n - 1) + n = \sum_{i = 1}^{n} {i}.
\end{align*}

式~\eqref{eq:B0102} 的 \(i\) 是求和指标,
其只起一个辅助的作用.
当我们还原式~\eqref{eq:B0102}
为式~\eqref{eq:B0101} 时,
求和指标 \(i\) 不应出现.
比如, 我们也可写式~\eqref{eq:B0101} 为
\begin{align*}
    \sum_{j = m}^{n} {a_j}.
\end{align*}
所以, 我们可用任何文字作求和指标, 除非此文字%
跟别的文字混淆.
比如, \(s\)~行 \(t\)~列的矩形数表
\begin{equation}
    \begin{matrix}
        a_{1,1} & a_{1,2} & \cdots & a_{1,t} \\
        a_{2,1} & a_{2,2} & \cdots & a_{2,t} \\
        \vdots  & \vdots  & {}     & \vdots  \\
        a_{s,1} & a_{s,2} & \cdots & a_{s,t} \\
    \end{matrix}
    \label{eq:B0103}
\end{equation}
的第~\(i\)~行的 \(t\)~个数的和是
\begin{align*}
    a_{i,1} + a_{i,2} + \dots + a_{i,t}
    = \sum_{j = 1}^{t} {a_{i,j}}.
\end{align*}
这里, 我们不能用文字 \(i\) 作求和指标,
因为
\begin{align*}
    \sum_{i = 1}^{t} {a_{i,i}}
\end{align*}
的意思是
\begin{align*}
    a_{1,1} + a_{2,2} + \dots + a_{t,t}.
\end{align*}

有时, 被加的数用二个或多个指标编号.
比如, 我们计算矩形数表~\eqref{eq:B0103} 的 \(st\)~个数的和 \(S\).
因为数的加法适合结合律与交换律,
故我们可按任何的次序求和.
特别地, 我们可以先求行~\(i\) 的 \(t\)~个数的和
\begin{align*}
    a_{i,1} + a_{i,2} + \dots + a_{i,t}
    = \sum_{j = 1}^{t} {a_{i,j}},
\end{align*}
再求每行的和的和, 得
\begin{align*}
    S
    = {} & \sum_{j = 1}^{t} {a_{1,j}}
    + \sum_{j = 1}^{t} {a_{2,j}}
    + \dots
    + \sum_{j = 1}^{t} {a_{s,j}}
    \\
    = {} &
    \sum_{i = 1}^{s}
        {\left( \sum_{j = 1}^{t} a_{i,j} \right)}.
\end{align*}
为方便, 我们写
\begin{align*}
    \sum_{i = 1}^{s}
        {\left( \sum_{j = 1}^{t} a_{i,j} \right)}
    = \sum_{i = 1}^{s}
        {\sum_{j = 1}^{t} {a_{i,j}}}.
\end{align*}
这就是 \(2\)~重求和.

当然, 我们还可以先求列~\(j\) 的 \(s\)~个数的和
\begin{align*}
    a_{1,j} + a_{2,j} + \dots + a_{s,j}
    = \sum_{i = 1}^{s} {a_{i,j}},
\end{align*}
再求每列的和的和, 得
\begin{align*}
    S
    = {} & \sum_{i = 1}^{s} {a_{i,1}}
    + \sum_{i = 1}^{s} {a_{i,2}}
    + \dots
    + \sum_{i = 1}^{s} {a_{i,t}}
    \\
    = {} &
    \sum_{j = 1}^{t}
        {\left( \sum_{i = 1}^{s} {a_{i,j}} \right)}
    \\
    = {} &
    \sum_{j = 1}^{t} {
            \sum_{i = 1}^{s} {a_{i,j}}}.
\end{align*}
比较二次计算的结果, 我们有
\begin{align*}
    \sum_{i = 1}^{s} {\sum_{j = 1}^{t} {a_{i,j}}}
    = \sum_{j = 1}^{t} {\sum_{i = 1}^{s} {a_{i,j}}}.
\end{align*}
通俗地, 我们可交换求和号的次序, 而不影响和.

类似地, 我们可引入 \(3\)~重求和
\begin{align*}
    \sum_{i = 1}^{s} {
            \sum_{j = 1}^{t} {
                    \sum_{k = 1}^{u} {
                            a_{i,j,k}}}}
    =
    \sum_{i = 1}^{s}
        {\left( \sum_{j = 1}^{t} {
                \sum_{k = 1}^{u} {
                    a_{i,j,k} }} \right)}.
\end{align*}
在此基础上, 我们可引入 \(4\)~重求和
\begin{align*}
    \sum_{i = 1}^{s} {
            \sum_{j = 1}^{t} {
                    \sum_{k = 1}^{u} {
                            \sum_{\ell = 1}^{v} {
                                    a_{i,j,k,\ell} }}}}
    =
    \sum_{i = 1}^{s}
        {\left(
            \sum_{j = 1}^{t} {
                \sum_{k = 1}^{u} {
                    \sum_{\ell = 1}^{v} {
                        a_{i,j,k,\ell} }}}
            \right)}.
\end{align*}
……
在此基础上, 我们可引入 \(p\)~重求和
\begin{align*}
    \sum_{i_1 = 1}^{n_1} {
            \sum_{i_2 = 1}^{n_2} {
                    \dots
                    \sum_{i_{p-1} = 1}^{n_{p-1}} {
                            \sum_{i_p = 1}^{n_p} {
                                    a_{i_1,i_2,\dots,i_{p-1},i_p} }}}}
    = \sum_{i_1 = 1}^{n_1}
        {\left(
            \sum_{i_2 = 1}^{n_2} {
                \dots
                \sum_{i_{p-1} = 1}^{n_{p-1}} {
                    \sum_{i_p = 1}^{n_p} {
                        a_{i_1,i_2,\dots,i_{p-1},i_p}}}}
            \right)}.
\end{align*}
特别地, 若 \(n_1 = n_2 = \dots = n_p = n\),
我们可简单地写
\begin{align*}
    \sum_{i_1 = 1}^{n} {
            \sum_{i_2 = 1}^{n} {
                    \dots
                    \sum_{i_{p-1} = 1}^{n} {
                            \sum_{i_p = 1}^{n} {
                                    a_{i_1,i_2,\dots,i_{p-1},i_p} }}}}
    =
    \sum_{i_1,i_2,\dots,i_p = 1}^{n}
        {a_{i_1,i_2,\dots,i_{p-1},i_p}}.
\end{align*}

有时, 虽然被加的数用若干个指标编号,
但被加的并不是全部,
而是指标适合某些条件的那一部分.
这时, 我们在求和号下写出指标适合的条件.
比如,
\begin{align*}
         & \sum_{1 \leq i < j \leq n} {a_{i,j}}
    \\
    = {} & \hphantom{{} + {}} a_{1,2}
    \\
         & + a_{1,3} + a_{2,3}
    \\
         & + a_{1,4} + a_{2,4} + a_{3,4}
    \\
         & +
    \dots
    \\
         & + a_{1,n} + a_{2,n} + \dots + a_{n-1,n}.
\end{align*}
再比如, 若 \(\ell\) 是某个不超过 \(n\) 的正整数, 则
\begin{align*}
    \sum_{\substack{1 \leq i \leq n \\i \neq \ell}}
    {a_i}
    = a_1 + \dots + a_{\ell-1} + a_{\ell+1} + \dots + a_n.
\end{align*}

设 \(a_{i_1, i_2, \dots, i_n}\) 是一些被编号的数.
设 \(R_1\), \(R_2\)
是关于指标 \(i_1\), \(i_2\), \(\dots\), \(i_n\) 的约束.
若不存在同时适合 \(R_1\), \(R_2\)
的指标 \(i_1\), \(i_2\), \(\dots\), \(i_n\),
则, 根据加法的结合律与交换律,
\begin{equation}
    \begin{aligned}
             & \sum_{i_1,i_2,\dots,i_n
            \,\text{适合}\,R_1\,\text{或}\,R_2}
        {a_{i_1, i_2, \dots, i_n}}
        \\
        = {} & \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,R_1}
        {a_{i_1, i_2, \dots, i_n}}
        + \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,R_2}
        {a_{i_1, i_2, \dots, i_n}}.
    \end{aligned}
    \label{eq:B0104}
\end{equation}
比如,
\begin{align*}
     & \sum_{1 \leq i \leq 10} {i}
    = \sum_{1 \leq i \leq 4} {i}
    + \sum_{5 \leq i \leq 10} {i};
    \\
     & \sum_{\substack{1 \leq i, j \leq n \\i \neq j}} {a_{i,j}}
    = \sum_{1 \leq i < j \leq n} {a_{i,j}}
    + \sum_{1 \leq j < i \leq n} {a_{i,j}}.
\end{align*}

当不存在指标适合约束 \(N\) 时
(也就是, \(N\) 是空约束时),
我们约定
\begin{equation}
    \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,N}
    {a_{i_1, i_2, \dots, i_n}} = 0.
    \label{eq:B0105}
\end{equation}
比如,
\begin{align*}
    \sum_{1 \leq i < j \leq 1} {a_{i,j}} = 0.
\end{align*}

为解释此约定, 我们任取一个约束 \(R\).
既然不存在指标适合约束 \(N\),
自然, 也不存在指标同时适合 \(N\), \(R\).
再注意,
``\(i_1\), \(i_2\), \(\dots\), \(i_n\)
适合 \(N\) 或 \(R\)''
相当于
``\(i_1\), \(i_2\), \(\dots\), \(i_n\)
适合 \(R\)''.
由式~\eqref{eq:B0104},
\begin{align*}
         &
    \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    \\
    = {} &
    \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,N\,\text{或}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    \\
    = {} &
    \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,N}
    {a_{i_1, i_2, \dots, i_n}}
    + \sum_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}.
\end{align*}
消去相同的项, 得式~\eqref{eq:B0105}.

\section{求积号}

为简便地表示求积,
人们聪明地作了\emph{求积号} \(\prod\).
对应拉丁字母 P, \(\prod\) 来自 \angla{product} (英语).

设 \(a_m\), \(a_{m+1}\), \(\dots\), \(a_n\) 是
\(n - m + 1\)~个数 (\(n \geq m\)).
我们可简单地写这 \(n - m + 1\)~个数的积
\begin{equation}
    a_m \cdot a_{m+1} \cdot \dots \cdot a_n
    \label{eq:B0201}
\end{equation}
为
\begin{equation}
    \prod_{i = m}^{n} {a_i}.
    \label{eq:B0202}
\end{equation}
比如,
\begin{align*}
     & 6 \cdot 5x \cdot 4x^2 \cdot 3x^3 \cdot 2x^4 \cdot x^5
    = \prod_{i = 0}^{5} {(6 - i)x^i};                        \\
     & 1 \cdot 2 \cdot \dots \cdot (n - 1) \cdot n
    = \prod_{i = 1}^{n} {i}.
\end{align*}

式~\eqref{eq:B0202} 的 \(i\) 是求积指标,
其只起一个辅助的作用.
当我们还原式~\eqref{eq:B0202}
为式~\eqref{eq:B0201} 时,
求积指标 \(i\) 不应出现.
比如, 我们也可写式~\eqref{eq:B0201} 为
\begin{align*}
    \prod_{j = m}^{n} {a_j}.
\end{align*}
所以, 我们可用任何文字作求积指标, 除非此文字%
跟别的文字混淆.
比如, \(s\)~行 \(t\)~列的矩形数表
\begin{equation}
    \begin{matrix}
        a_{1,1} & a_{1,2} & \cdots & a_{1,t} \\
        a_{2,1} & a_{2,2} & \cdots & a_{2,t} \\
        \vdots  & \vdots  & {}     & \vdots  \\
        a_{s,1} & a_{s,2} & \cdots & a_{s,t} \\
    \end{matrix}
    \label{eq:B0203}
\end{equation}
的第~\(i\)~行的 \(t\)~个数的积是
\begin{align*}
    a_{i,1} \cdot a_{i,2} \cdot \dots \cdot a_{i,t}
    = \prod_{j = 1}^{t} {a_{i,j}}.
\end{align*}
这里, 我们不能用文字 \(i\) 作求积指标,
因为
\begin{align*}
    \prod_{i = 1}^{t} {a_{i,i}}
\end{align*}
的意思是
\begin{align*}
    a_{1,1} \cdot a_{2,2} \cdot \dots \cdot a_{t,t}.
\end{align*}

有时, 被乘的数用二个或多个指标编号.
比如, 我们计算矩形数表~\eqref{eq:B0203} 的 \(st\)~个数的积 \(P\).
因为数的乘法适合结合律与交换律,
故我们可按任何的次序求积.
特别地, 我们可以先求行~\(i\) 的 \(t\)~个数的积
\begin{align*}
    a_{i,1} \cdot a_{i,2} \cdot \dots \cdot a_{i,t}
    = \prod_{j = 1}^{t} {a_{i,j}},
\end{align*}
再求每行的积的积, 得
\begin{align*}
    P
    = {} & \prod_{j = 1}^{t} {a_{1,j}}
    \cdot \prod_{j = 1}^{t} {a_{2,j}}
    \cdot \dots
    \cdot \prod_{j = 1}^{t} {a_{s,j}}
    \\
    = {} &
    \prod_{i = 1}^{s}
        {\left( \prod_{j = 1}^{t} {a_{i,j}} \right)}.
\end{align*}
为方便, 我们写
\begin{align*}
    \prod_{i = 1}^{s}
        {\left( \prod_{j = 1}^{t} {a_{i,j}} \right)}
    = \prod_{i = 1}^{s}
        {\prod_{j = 1}^{t} {a_{i,j}}}.
\end{align*}
这就是 \(2\)~重求积.

当然, 我们还可以先求列~\(j\) 的 \(s\)~个数的积
\begin{align*}
    a_{1,j} \cdot a_{2,j} \cdot \dots \cdot a_{s,j}
    = \prod_{i = 1}^{s} {a_{i,j}},
\end{align*}
再求每列的积的积, 得
\begin{align*}
    P
    = {} & \prod_{i = 1}^{s} {a_{i,1}}
    \cdot \prod_{i = 1}^{s} {a_{i,2}}
    \cdot \dots
    \cdot \prod_{i = 1}^{s} {a_{i,t}}
    \\
    = {} &
    \prod_{j = 1}^{t}
        {\left( \prod_{i = 1}^{s} {a_{i,j}} \right)}
    \\
    = {} &
    \prod_{j = 1}^{t}
        {\prod_{i = 1}^{s} {a_{i,j}}}.
\end{align*}
比较二次计算的结果, 我们有
\begin{align*}
    \prod_{i = 1}^{s} {\prod_{j = 1}^{t} {a_{i,j}}}
    = \prod_{j = 1}^{t} {\prod_{i = 1}^{s} {a_{i,j}}}.
\end{align*}
通俗地, 我们可交换求积号的次序, 而不影响积.

类似地, 我们可引入 \(3\)~重求积
\begin{align*}
    \prod_{i = 1}^{s} {
            \prod_{j = 1}^{t} {
                    \prod_{k = 1}^{u} {
                            a_{i,j,k} }}}
    =
    \prod_{i = 1}^{s}
        {\left(
            \prod_{j = 1}^{t} {
                \prod_{k = 1}^{u} {
                    a_{i,j,k} }}
            \right)}.
\end{align*}
在此基础上, 我们可引入 \(4\)~重求积
\begin{align*}
    \prod_{i = 1}^{s} {
            \prod_{j = 1}^{t} {
                    \prod_{k = 1}^{u} {
                            \prod_{\ell = 1}^{v} {
                                    a_{i,j,k,\ell} }}}}
    =
    \prod_{i = 1}^{s}
        {\left(
            \prod_{j = 1}^{t} {
                \prod_{k = 1}^{u} {
                    \prod_{\ell = 1}^{v} {
                        a_{i,j,k,\ell} }}}
            \right)}.
\end{align*}
……
在此基础上, 我们可引入 \(p\)~重求积
\begin{align*}
    \prod_{i_1 = 1}^{n_1} {
            \prod_{i_2 = 1}^{n_2} {
                    \dots
                    \prod_{i_{p-1} = 1}^{n_{p-1}} {
                            \prod_{i_p = 1}^{n_p} {
                                    a_{i_1,i_2,\dots,i_{p-1},i_p} }}}}
    = \prod_{i_1 = 1}^{n_1}
        {\left(
            \prod_{i_2 = 1}^{n_2} {
                \dots
                \prod_{i_{p-1} = 1}^{n_{p-1}} {
                    \prod_{i_p = 1}^{n_p} {
                        a_{i_1,i_2,\dots,i_{p-1},i_p} }}}
            \right)}.
\end{align*}
特别地, 若 \(n_1 = n_2 = \dots = n_p = n\),
我们可简单地写
\begin{align*}
    \prod_{i_1 = 1}^{n} {
            \prod_{i_2 = 1}^{n} {
                    \dots
                    \prod_{i_{p-1} = 1}^{n} {
                            \prod_{i_p = 1}^{n} {
                                    a_{i_1,i_2,\dots,i_{p-1},i_p} }}}}
    =
    \prod_{i_1,i_2,\dots,i_p = 1}^{n}
        {a_{i_1,i_2,\dots,i_{p-1},i_p}}.
\end{align*}

有时, 虽然被乘的数用若干个指标编号,
但被乘的并不是全部,
而是指标适合某些条件的那一部分.
这时, 我们在求积号下写出指标适合的条件.
比如,
\begin{align*}
         & \prod_{1 \leq i < j \leq n} {a_{i,j}}
    \\
    = {} & \hphantom{{} \cdot {}} a_{1,2}
    \\
         & \cdot a_{1,3} \cdot a_{2,3}
    \\
         & \cdot a_{1,4} \cdot a_{2,4} \cdot a_{3,4}
    \\
         & \cdot
    \dots
    \\
         & \cdot a_{1,n} \cdot a_{2,n}
    \cdot \dots \cdot a_{n-1,n}.
\end{align*}
再比如, 若 \(\ell\) 是某个不超过 \(n\) 的正整数, 则
\begin{align*}
    \prod_{\substack{1 \leq i \leq n \\i \neq \ell}}
    {a_i}
    = a_1 \cdot \dots \cdot a_{\ell-1}
    \cdot a_{\ell+1} \cdot \dots \cdot a_n.
\end{align*}

设 \(a_{i_1, i_2, \dots, i_n}\) 是一些被编号的数.
设 \(R_1\), \(R_2\)
是关于指标 \(i_1\), \(i_2\), \(\dots\), \(i_n\) 的约束.
若不存在同时适合 \(R_1\), \(R_2\)
的指标 \(i_1\), \(i_2\), \(\dots\), \(i_n\),
则, 根据乘法的结合律与交换律,
\begin{equation}
    \begin{aligned}
             & \prod_{i_1,i_2,\dots,i_n
            \,\text{适合}\,R_1\,\text{或}\,R_2}
        {a_{i_1, i_2, \dots, i_n}}
        \\
        = {} & \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R_1}
        {a_{i_1, i_2, \dots, i_n}}
        \cdot \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R_2}
        {a_{i_1, i_2, \dots, i_n}}.
    \end{aligned}
    \label{eq:B0204}
\end{equation}
比如,
\begin{align*}
     & \prod_{1 \leq i \leq 10} {i}
    = \prod_{1 \leq i \leq 4} {i}
    \cdot \prod_{5 \leq i \leq 10} {i};
    \\
     & \prod_{\substack{1 \leq i, j \leq n \\i \neq j}} {a_{i,j}}
    = \prod_{1 \leq i < j \leq n} {a_{i,j}}
    \cdot \prod_{1 \leq j < i \leq n} {a_{i,j}}.
\end{align*}

当不存在指标适合约束 \(N\) 时
(也就是, \(N\) 是空约束时),
我们约定
\begin{equation}
    \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,N}
    {a_{i_1, i_2, \dots, i_n}} = 1.
    \label{eq:B0205}
\end{equation}
比如,
\begin{align*}
    \prod_{1 \leq i < j \leq 1} {a_{i,j}} = 1.
\end{align*}

为解释此约定, 我们设
\begin{align*}
    x = \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,N}
    {a_{i_1, i_2, \dots, i_n}}.
\end{align*}
我们任取一个约束 \(R\).
既然不存在指标适合约束 \(N\),
自然, 也不存在指标同时适合 \(N\), \(R\).
再注意,
``\(i_1\), \(i_2\), \(\dots\), \(i_n\)
适合 \(N\) 或 \(R\)''
相当于
``\(i_1\), \(i_2\), \(\dots\), \(i_n\)
适合 \(R\)''.
由式~\eqref{eq:B0204},
\begin{align*}
         &
    \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    \\
    = {} &
    \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,N\,\text{或}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    \\
    = {} &
    \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,N}
    {a_{i_1, i_2, \dots, i_n}}
    \cdot \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}.
\end{align*}
特别地, 代 \(R\) 以 \(N\), 有 \(x = x \cdot x\),
即 \(x = 0\) 或 \(x = 1\).
若我们取 \(x = 0\),
则对任何的约束~\(R\),
必有
\begin{align*}
    \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    = 0
    \cdot \prod_{i_1,i_2,\dots,i_n\,\text{适合}\,R}
    {a_{i_1, i_2, \dots, i_n}}
    = 0.
\end{align*}
于是, 若我们取 \(x = 0\),
则任何多个数的积都是 \(0\).
这是不合理的.
所以, 我们取 \(x = 1\);
也就是, 我们约定式~\eqref{eq:B0205}.

\vspace{2ex}

或许, 您已发现, 因为数的加法跟乘法%
都适合结合律与交换律,
故求和号与求积号有类似的性质.

\section{数学归纳法}

% Mathematical induction is a way of
% proving propositions deductively.
\emph{数学归纳法}是一个证明命题的方法.

\begin{principle}[数学归纳法]
    设 \(P(n)\) 是跟整数~\(n\) 有关的句子.
    设存在一个整数 \(n_0\) 使:

    (1)
    (起始步)
    \(P(n_0)\) 是对的;

    (2)
    (递推步)
    对每个不低于 \(n_0\) 的整数 \(n\),
    ``若 \(P(n)\) 是对的, 则 \(P(n+1)\) 是对的''
    是对的.

    那么, 对每个不低于 \(n_0\) 的整数 \(n\),
    \(P(n)\) 是对的.
\end{principle}

通俗地, 我们可视每个 \(P(n)\) 为一本竖立的书.
我们视 ``\(P(n)\) 是对的'' 为
``第~\(n\)~本书倒下''.
假定, 我们推倒了第~\(1\)~本书 \(P(1)\) (这对应起始步),
且一本书倒下总会使%
跟在它后面的那一本书倒下 (这对应递推步).
那么, 第~\(1\)~本书, 与后面的书,
都应倒下.

\vspace{2ex}

我们看一个具体的例.

\begin{example}
    设 \(n\) 是正整数.
    用数学归纳法证明
    \begin{equation}
        1 + 3 + \dots + (2n - 1) = n^2.
        \label{eq:B0301}
    \end{equation}

    既然, 我们要证, 对正整数 \(n\),
    式~\eqref{eq:B0301} 是对的,
    我们可试取 \(n_0 = 1\),
    并设命题 \(P(n)\): \(1 + 3 + \dots + (2n - 1) = n^2\).
    我们验证数学归纳法的条件,
    即起始步与递推步,
    是否都成立.

    (1)
    \(P(n_0)\) 即 \(P(1)\), 即 \(1 = 1^2\).
    这显然是对的.
    故起始步成立.

    (2)
    我们假定 \(P(n)\) 是对的, 其中, \(n \geq n_0 = 1\).
    我们要由此证明 \(P(n+1)\) 也是对的:
    \begin{align*}
             & 1 + 3 + \dots + (2n - 1) + (2(n+1) - 1)
        \\
        = {} & (1 + 3 + \dots + (2n - 1)) + (2n + 1)
        \\
        = {} & n^2 + (2n + 1)
        \\
        = {} & (n + 1)^2.
    \end{align*}
    其中, 从行~2 到行~3,
    我们用到了 ``\(P(n)\) 是对的'' 的假定
    (我们叫这样的假定为\emph{归纳假定}).
    所以, (若 \(P(n)\) 是对的, 则) \(P(n+1)\) 是对的.
    故递推步成立.

    由数学归纳法, \(P(n)\) 对%
    任何正整数~\(n\) 都是成立的.
\end{example}

% 注意, 数学归纳法只是证明命题的一个方法.
% 其实, 我们可用更简单的方法证式~\eqref{eq:B0301}.
% 我们记
% \begin{align*}
%     S_n = 1 + 3 + \dots + (2(n-1) - 1) + (2n - 1).
% \end{align*}
% 因为数的加法适合结合律与交换律, 故
% \begin{align*}
%     S_n = (2n - 1) + (2(n-1) - 1) + \dots + 3 + 1.
% \end{align*}
% 从而, 仍由结合律与交换律,
% \begin{align*}
%     2S_n = (1 + (2n - 1)) + (3 + (2(n-1) - 1))
%     + \dots + ((2n - 1) + 1) = 2n \cdot n.
% \end{align*}
% 由此可知 \(S_n = n^2\).

% \vspace{2ex}

注意, 数学归纳法的起始步与递推步是缺一不可的.
我们看二个例.

\begin{example}[缺起始步]
    设 \(n\)~是正整数.
    用数学归纳法 ``证明''
    \begin{equation}
        1 + 3 + \dots + (2n - 1) = n^2 + 1.
        \label{eq:B0302}
    \end{equation}

    既然, 我们要证, 对正整数 \(n\),
    式~\eqref{eq:B0302} 是对的,
    我们可试取 \(n_0 = 1\),
    并设命题 \(P'(n)\): \(1 + 3 + \dots + (2n - 1) = n^2 + 1\).
    我们验证数学归纳法的条件,
    即起始步与递推步,
    是否都成立.

    (1)
    \(P'(n_0)\) 即 \(P'(1)\), 即 \(1 = 1^2 + 1\).
    这显然是对的.
    % (请允许我暂时 ``胡说'').
    故起始步成立.

    (2)
    我们假定 \(P'(n)\) 是对的, 其中, \(n \geq n_0 = 1\).
    我们要由此证明 \(P'(n+1)\) 也是对的:
    \begin{align*}
             & 1 + 3 + \dots + (2n - 1) + (2(n+1) - 1)
        \\
        = {} & (1 + 3 + \dots + (2n - 1)) + (2n + 1)
        \\
        = {} & (n^2 + 1) + (2n + 1)
        \\
        = {} & (n + 1)^2 + 1.
    \end{align*}
    其中, 从行~2 到行~3,
    我们用到了 ``\(P'(n)\) 是对的'' 的假定.
    所以, (若 \(P'(n)\) 是对的, 则) \(P'(n+1)\) 是对的.
    故递推步成立.

    所以, 由数学归纳法,
    式~\eqref{eq:B0302} 是对的.
    可是, 式~\eqref{eq:B0302} 不可能是对的!
    上个例说,
    \(1 + 3 + \dots + (2n-1) = n^2\),
    而 \(n^2\) 跟 \(n^2 + 1\) 不可能相等.

    我在何地方出了问题?
    不难看出, 起始步不是对的:
    我错误地认为 \(P'(1)\) 是对的.

    由此可见, 数学归纳法的起始步是不可少的.
\end{example}

\begin{example}[缺递推步]
    用数学归纳法 ``证明'' 命题 \(Q(n)\) (\(n\) 为正整数):
    对任何 \(n\)~个数 \(a_1\), \(a_2\), \(\dots\), \(a_n\),
    它 (们) 都相等.

    既然, 我们要证, 对正整数 \(n\),
    \(Q(n)\) 是对的,
    我们可试取 \(n_0 = 1\).
    我们验证数学归纳法的条件,
    即起始步与递推步,
    是否都成立.

    (1)
    \(Q(n_0)\) 即 \(Q(1)\), 即:
    对任何 \(1\)~个数 \(a_1\), 它 (们) 都相等.
    一般地, 我们认为, 一个数总等于自己.
    所以, \(Q(1)\) 是对的.
    故起始步成立.

    (2)
    我们假定 \(Q(n)\) 是对的, 其中, \(n \geq n_0 = 1\).
    我们要由此证明 \(Q(n+1)\) 也是对的.
    任取 \(n+1\)~个数
    \(a_1\), \(a_2\), \(\dots\), \(a_n\), \(a_{n+1}\).
    考虑这~\(n+1\)~个数的前~\(n\)~个:
    \(a_1\), \(a_2\), \(\dots\), \(a_n\).
    因为 \(Q(n)\) 是对的, 故
    \begin{align*}
        a_1 = a_2 = \dots = a_n.
    \end{align*}
    再考虑这~\(n+1\)~个数的后~\(n\)~个:
    \(a_2\), \(\dots\), \(a_n\), \(a_{n+1}\).
    仍因 \(Q(n)\) 是对的, 故
    \begin{align*}
        a_2 = \dots = a_n = a_{n+1}.
    \end{align*}
    既然 \(a_1 = a_2\), \(\dots\), \(a_n = a_{n+1}\), 故
    \begin{align*}
        a_1 = a_2 = \dots = a_n = a_{n+1}.
    \end{align*}
    所以, (若 \(Q(n)\) 是对的, 则) \(Q(n+1)\) 是对的.
    故递推步成立.

    所以, 由数学归纳法,
    对每个正整数 \(n\), \(Q(n)\) 是对的.
    可是, 这不合常识:
    \(0\) 与 \(1\) 就是不相同的二个数.

    我在何地方出了问题?
    其实, \(Q(1)\) 是不能推出 \(Q(2)\) 的.
    不过, \(Q(2)\) 的确可推出 \(Q(3)\);
    进一步地, 不难看出, 对每个不低于 \(2\) 的整数 \(n\),
    ``若 \(Q(n)\) 是对的, 则 \(Q(n+1)\) 是对的''
    是对的.
    虽然如此,
    因存在一个不低于 \(n_0\) 的整数 \(1\),
    使 ``若 \(Q(1)\) 是对的, 则 \(Q(2)\) 是对的''
    是错的,
    故递推步不成立.

    由此可见, 数学归纳法的递推步也是不可少的.
\end{example}

最后, 我用二个难的例%
助您更好地理解与运用数学归纳法.

\begin{example}
    设数列 \(a_1\), \(a_2\), \(\dots\), \(a_n\), \(\dots\) 适合
    \begin{align*}
        a_n =
        \begin{cases}
            1,                  & n = 1;    \\
            1,                  & n = 2;    \\
            a_{n-1} + 2a_{n-2}, & n \geq 3.
        \end{cases}
    \end{align*}
    用数学归纳法证明,
    对任何正整数 \(n\),
    \begin{align*}
        a_n = \frac{2^n - (-1)^n}{3}.
    \end{align*}

    我们试取 \(n_0 = 1\),
    并设命题 \(P(n)\): \(a_n = (2^n - (-1)^n)/3\).
    验证起始步时, 没有问题:
    \begin{align*}
        \frac{2^1 - (-1)^1}{3} = \frac{3}{3} = 1 = a_1.
    \end{align*}
    可是, 在验证递推步时,
    我们发现,
    我们无法由 \(P(1)\) 推出 \(P(2)\):
    此数列的前 \(2\)~项被定义为 \(1\),
    故 \(a_1\) 跟 \(a_2\) 无关.

    那么, 既然选 \(n_0\) 为 \(1\) 不是好的,
    我们能否选 \(n_0\) 为 \(2\)?
    首先, \(P(2)\) 也是对的:
    \begin{align*}
        \frac{2^2 - (-1)^2}{3} = \frac{3}{3} = 1 = a_2.
    \end{align*}
    可是,
    我们仍无法由 \(P(n)\) 推出 \(P(n+1)\)
    (其中, \(n \geq 2\)).
    我们假定 \(P(n)\) 是对的;
    或者, 我们假定 \(a_n = (2^n - (-1)^n)/3\).
    我们要证 \(a_{n+1} = (2^{n+1} - (-1)^{n+1})/3\).
    根据此数列的定义,
    \(a_{n+1} = a_n + 2a_{n-1}\).
    我们可代 \(a_n\) 以归纳假定,
    但 \(a_{n-1}\) 不可被代.

    我们无妨考虑用数学归纳法证明命题
    \(Q(n)\):
    \(P(n)\) 与 \(P(n+1)\) 是对的.

    首先, \(Q(1)\) 是对的; 我们验证过.

    然后, 我们假定 \(Q(n)\) 是对的.
    我们要由此证明 \(Q(n+1)\) 是对的.
    既然 \(Q(n)\) 是对的, 那么 \(P(n)\) 跟 \(P(n+1)\) 都是对的.
    为了证明 \(Q(n+1)\) 是对的, 我们要证
    \(P(n+1)\) 与 \(P((n+1)+1)\),
    即 \(P(n+1)\) 与 \(P(n+2)\) 都是对的.
    根据假定, \(P(n+1)\) 是对的.
    我们只要证 \(P(n+2)\) 也是对的,
    即可知, \(Q(n+1)\) 是对的:
    \begin{align*}
        a_{n+2}
        = {} & a_{n+1} + 2a_n
        \\
        = {} & \frac{2^{n+1} - (-1)^{n+1}}{3}
        + 2 \cdot \frac{2^n - (-1)^n}{3}
        \\
        = {} & \frac{2}{3} \cdot 2^n + \frac{1}{3} \cdot (-1)^n
        + \frac{2}{3} \cdot 2^n - \frac{2}{3} \cdot (-1)^n
        \\
        = {} & \frac{4}{3} \cdot 2^n - \frac{1}{3} \cdot (-1)^n
        \\
        = {} & \frac{2^{n+2} - (-1)^{n+2}}{3}.
    \end{align*}
    所以, (若 \(Q(n)\) 是对的, 则) \(Q(n+1)\) 是对的.

    由数学归纳法, \(Q(n)\) 对%
    任何正整数~\(n\) 都是成立的.
    进而, \(P(n)\) 对任何正整数~\(n\) 是成立的.

    当然, 我们还可考虑, 用数学归纳法%
    证命题 \(R(n)\)
    (\(n\) 为不低于 \(2\) 的整数):
    对任何不超过 \(n\) 的正整数 \(k\),
    \(P(k)\) 是对的.
    (这里, \(n_0 = 2\);
    我留它为您的习题.)
    这样, 我们也能证明,
    \(P(n)\) 对任何正整数 \(n\) 是成立的.

    由此可见:

    (1)
    不是每个跟整数相关的命题%
    都能直接地被数学归纳法证明.

    (2)
    有时, 为运用数学归纳法,
    我们要恰当地作辅助命题.

    (3)
    有时, 辅助命题的作法多于一个.
\end{example}

\begin{example}
    设 \(a\), \(b\) 是正整数.
    若存在正整数 \(c\) 使 \(a = bc\),
    我们说, \(b\) 是 \(a\) 的一个\emph{因子}.

    不难看出, 若 \(b\) 是 \(a\) 的一个因子,
    则 \(1 \leq b \leq a\).

    注意, 对任何正整数 \(a\),
    \(a = 1a = a1\).
    则每个正整数 \(a\) 都有因子 \(1\), \(a\)
    (注意, \(1\) 与 \(a\) 不一定是二个互不相同的数,
    除非 \(a > 1\)).
    我们说, \(1\) 与 \(a\) 是 \(a\) 的\emph{平凡的因子}.
    若 \(b\) 是 \(a\) 的因子,
    \(b \neq 1\),
    且 \(b \neq a\),
    则 \(b\) 是 \(a\) 的一个\emph{不平凡的因子}.

    不难看出, 若 \(b\) 是 \(a\) 的一个不平凡的因子,
    则 \(1 < b < a\).

    设正整数 \(a > 1\).
    若 \(a\) 有不平凡的因子,
    则 \(a\) 是一个\emph{可约的数};
    若 \(a\) 没有不平凡的因子
    (也就是, \(a\) 有且只有平凡的因子),
    我们说, \(a\) 是一个\emph{不可约的数}.
    比如, \(4\), \(6\), \(8\), \(9\), \(39\) 都是可约的数.
    但 \(2\), \(3\), \(5\), \(7\), \(37\) 都是不可约的数,

    注意, 根据定义,
    \(1\) 不是可约的数, 且不是不可约的数.

    我们证明,
    可写一个高于 \(1\)~的整数为若干个不可约的数的积.
    具体地, 设命题 \(P(n)\):
    存在若干个不可约的数
    \(p_1\), \(p_2\), \(\dots\), \(p_k\) 使
    \begin{align*}
        n = p_1 p_2 \dots p_k.
    \end{align*}
    那么, 我们的目标就是,
    当 \(n \geq 2\) 时,
    \(P(n)\) 是对的.

    我们试直接用数学归纳法证 \(P(n)\).
    取 \(n_0 = 2\).
    因为 \(2\) 是一个不可约的数,
    故它当然是一个不可约的数的积 (即自己).
    不过, 我们似乎无法由
    \(P(n)\) 推出 \(P(n+1)\),
    因为, \(n\) 跟 \(n+1\) 的因子%
    似乎没有有意思的关系.
    (因子的定义跟乘法有关, 而跟加法的关系不那么大.
    比如, 即使知道 \(2\) 是 \(n\) 的因子,
    但知道 \(n+1\) 的不平凡的因子或许是难的.)

    我们试作辅助命题 \(Q(n)\):
    \(P(n)\) 与 \(P(n+1)\) 是对的.
    取 \(n_0 = 2\).
    不难验证, \(Q(n_0)\) 是对的.
    不过, 我们似乎仍无法由
    \(Q(n)\) 推出 \(Q(n+1)\).

    现在, 您看我解此题.
    我作辅助命题 \(R(n)\):
    对每个高于 \(1\) 且不低于 \(n\) 的整数 \(i\),
    \(P(i)\) 是对的.
    现在, 我要用数学归纳法证,
    当 \(n \geq 2\) 时, \(R(n)\) 是对的.

    取 \(n_0 = 2\).
    不难验证, \(R(n_0)\) 是对的.

    现在, 设 \(R(m-1)\) 是对的.
    我要由此证 \(R(m)\) 也是对的.
    % (这跟 ``设 \(R(n)\) 是对的,
    % 由此证 \(R(n+1)\) 是对的''
    % 的本质是一样的;
    % 我只是换 \(n\) 为 \(m-1\).
    % \(n\), \(m-1\) 只是编号.)

    因为 \(R(m-1)\) 是对的,
    故 \(P(2)\), \(\dots\), \(P(m-1)\) 都是对的.
    所以, 若我们能由此证明 \(P(m)\) 是对的,
    则 \(R(m)\) 是对的.

    若 \(m\) 是一个不可约的数,
    则 \(m\) 当然是一个不可约的数的积 (即自己).
    那, 若 \(m\) 是一个可约的数, 会如何?
    既然 \(m\) 是一个可约的数,
    那么, 按定义, 它有不平凡的因子 \(b\);
    也就是, 存在一个高于 \(1\), 且低于 \(m\) 的整数 \(b\),
    与一个整数 \(c\),
    使 \(m = bc\).
    不难看出,
    此 \(c\) 也是高于 \(1\), 且低于 \(m\) 的.
    所以, \(P(b)\), \(P(c)\) 是对的.
    则存在不可约的数
    \(p_1\), \(\dots\), \(p_u\)
    使 \(b = p_1 \dots p_u\),
    且存在不可约的数
    \(p_{u+1}\), \(\dots\), \(p_v\)
    使 \(c = p_{u+1} \dots p_v\).
    从而
    \begin{align*}
        m = bc = p_1 \dots p_u p_{u+1} \dots p_v
    \end{align*}
    也是若干个不可约的数的积.

    由此可见, \(R(m)\) 是对的.

    由数学归纳法, \(R(n)\) 对%
    任何高于 \(1\) 的整数~\(n\) 都是成立的.
    进而, \(P(n)\) 对任何高于 \(1\) 的整数~\(n\) 是成立的.
\end{example}

\section{数的整数次方}

为简便地表示一个数自乘多次,
人们聪明地作了次方.

\begin{definition}
    设 \(x\) 是数.
    设 \(m\) 是非负整数.
    定义 \(x\) 的 \(m\)~\emph{次方}
    \begin{align*}
        x^m =
        \begin{cases}
            1,         & m = 0;    \\
            x^{m-1} x, & m \geq 1.
        \end{cases}
    \end{align*}
\end{definition}

不难看出, \(x^1 = x^0 x = 1 x = x\).

\begin{example}
    设 \(m\) 是非负整数.
    我们用数学归纳法证明,
    \(1^m = 1\).

    作命题 \(P(m)\):
    \(1^m = 1\).
    我们的目标是,
    对任何非负整数 \(m\), \(P(m)\) 是对的.

    \(P(0)\) 是对的, 因为
    \(1^0 = 1\).

    假定 \(P(m)\) 是对的.
    我们由此证明, \(P(m+1)\) 也是对的.
    注意, \(1^{m+1} = 1^m \cdot 1 = 1 \cdot 1 = 1\).

    所以, \(P(m+1)\) 是对的.
    由数学归纳法, 待证命题成立.
\end{example}

\begin{theorem}
    设 \(x\), \(y\) 是数.
    设 \(m\), \(\ell\) 是非负整数.
    则

    (1)
    \(x^{\ell+m} = x^{\ell} x^{m}\);

    (2)
    \((x^{\ell})^{m} = x^{\ell m}\);

    (3)
    \((x y)^{m} = x^m y^m\).
\end{theorem}

\begin{proof}
    我们用数学归纳法证明它们.

    (1)
    作命题 \(P(m)\):
    \(x^{\ell+m} = x^{\ell} x^{m}\).
    我们的目标是,
    对任何非负整数 \(m\), \(P(m)\) 是对的.

    \(P(0)\) 是对的, 因为
    \(x^{\ell+0} = x^{\ell} = x^{\ell} 1 = x^{\ell} x^{0}\).

    假定 \(P(m)\) 是对的.
    我们由此证明, \(P(m+1)\) 也是对的.
    注意,
    \begin{align*}
        x^{\ell+(m+1)}
        = x^{(\ell+m)+1}
        = x^{\ell+m} x
        = (x^{\ell} x^{m}) x
        = x^{\ell} (x^{m} x)
        = x^{\ell} x^{m+1}.
    \end{align*}
    所以, \(P(m+1)\) 是对的.
    由数学归纳法, 待证命题成立.

    (2)
    作命题 \(Q(m)\):
    \((x^{\ell})^{m} = x^{\ell m}\).
    我们的目标是,
    对任何非负整数 \(m\), \(Q(m)\) 是对的.

    \(Q(0)\) 是对的, 因为
    \((x^{\ell})^{0} = 1 = x^{0} = x^{\ell 0}\).

    假定 \(Q(m)\) 是对的.
    我们由此证明, \(Q(m+1)\) 也是对的.
    注意,
    \begin{align*}
        (x^{\ell})^{m+1}
        = (x^{\ell})^{m} x^{\ell}
        = x^{\ell m} x^{\ell}
        = x^{\ell m + \ell}
        = x^{\ell (m+1)}.
    \end{align*}
    所以, \(Q(m+1)\) 是对的.
    由数学归纳法, 待证命题成立.

    (3)
    作命题 \(R(m)\):
    \((x y)^{m} = x^{m} y^{m}\).
    我们的目标是,
    对任何非负整数 \(m\), \(R(m)\) 是对的.

    \(R(0)\) 是对的, 因为
    \((x y)^0 = 1 = 1 \cdot 1 = x^0 y^0\).

    假定 \(R(m)\) 是对的.
    我们由此证明, \(R(m+1)\) 也是对的.
    注意,
    \begin{align*}
        (x y)^{m+1}
        = {} &
        (x y)^{m} (x y)
        = (x^{m} y^{m}) (x y)
        = ((x^{m} y^{m}) x) y
        = (x^{m} (y^{m} x)) y
        \\
        = {} &
        (x^{m} (x y^{m})) y
        = ((x^{m} x) y^{m}) y
        = x^{m+1} (y^{m} y)
        = x^{m+1} y^{m+1}.
    \end{align*}
    所以, \(R(m+1)\) 是对的.
    由数学归纳法, 待证命题成立.
\end{proof}

以上, 我们讨论了数的非负整数次方.
若一个数不是 \(0\), 我们还能讨论它的负整数次方,
故我们能讨论它的整数次方.

\begin{definition}
    设 \(x\) 是数, 且 \(x \neq 0\).
    设 \(m\) 是整数.

    (1)
    设 \(m \geq 0\).
    则 \(x\) 的 \(m\)~次方 \(x^m\) 已被定义.

    (2)
    设 \(m < 0\).
    因为 \(x \neq 0\),
    故有 (唯一的) 数 \(u\) 使 \(ux = 1 = xu\).
    我们定义 \(x\) 的 \(m\)~次方 \(x^m\)
    为 \(u\) 的 \(-m\)~次方 \(u^{-m}\).
\end{definition}

\begin{example}
    设 \(m\) 是负整数.
    设 \(x\) 是 \(1\) 或 \(-1\).
    我们计算 \(x^m\).

    因为 \(x\) 适合 \(x x = 1 = x x\),
    故, 由定义, \(x^m = x^{-m}\).

    若 \(x = 1\), 则 \(1^m = 1^{-m} = 1\).
    由此可见, 对任何整数 \(n\), 有 \(1^n = 1\).
\end{example}

不难看出, 若 \(x \neq 0\),
则 \(x^{-1} = u^{-(-1)} = u\).
则 \(x^{-1} x = 1 = x x^{-1}\).

不是 \(0\) 的数的整数次方也有%
跟数的非负整数次方的性质类似的性质.
不过, 它们的证明是较复杂的.

\begin{theorem}
    设 \(x\), \(y\) 是数, 且都不是 \(0\).
    设 \(m\), \(\ell\) 是整数.
    则

    (1)
    \(x^{\ell+m} = x^{\ell} x^{m}\);

    (2)
    \((x^{\ell})^{m} = x^{\ell m}\);

    (3)
    \((x y)^{m} = x^m y^m\).
\end{theorem}

\begin{proof}
    以下,
    设 (唯一的) 数 \(u\) 适合 \(ux = 1 = xu\),
    且设 (唯一的) 数 \(v\) 适合 \(vy = 1 = yv\).
    我们先证 (2);
    我们再证 (3);
    我们最后证 (1).

    (2)
    分类讨论.
    设 \(\ell \geq 0\), 且 \(m \geq 0\).
    则我们已证此情形.

    设 \(\ell \geq 0\), 且 \(m < 0\).
    则 \(\ell \geq 0\), 且 \(-m > 0\).
    因为 \(x \neq 0\), 故 \(x^\ell \neq 0\).
    则有 (唯一的) 数 \(U\) 使 \(U x^\ell = 1 = x^\ell U\).
    注意,
    \(u^\ell x^\ell = (u x)^\ell = 1^\ell = 1\),
    且
    \(x^\ell u^\ell = (x u)^\ell = 1^\ell = 1\),
    故 \(U = u^\ell\).
    则 \((x^\ell)^m = U^{-m} = (u^\ell)^{-m}
    = u^{\ell (-m)}\).
    另一方面, 因为 \(\ell m \leq 0\),
    故 \(x^{\ell m} = u^{-(\ell m)} = u^{\ell (-m)}\).
    故 \((x^\ell)^m = u^{\ell (-m)} = x^{\ell m}\).

    设 \(\ell < 0\), 且 \(m \geq 0\).
    则 \(-\ell > 0\), 且 \(m \geq 0\).
    则 \(x^\ell = u^{-\ell}\).
    则 \((x^\ell)^m = (u^{-\ell})^m = u^{(-\ell) m}\).
    另一方面, 因为 \(\ell m \leq 0\),
    故 \(x^{\ell m} = u^{-(\ell m)} = u^{(-\ell) m}\).
    故 \((x^\ell)^m = u^{(-\ell) m} = x^{\ell m}\).

    设 \(\ell < 0\), 且 \(m < 0\).
    则 \(-\ell > 0\), 且 \(-m > 0\).
    则 \(x^\ell = u^{-\ell}\).
    因为 \(u \neq 0\), 故 \(u^{-\ell} \neq 0\).
    则有 (唯一的) 数 \(X\) 使
    \(X u^{-\ell} = 1 = u^{-\ell} X\).
    注意,
    \(x^{-\ell} u^{-\ell} = (x u)^{-\ell} = 1^{-\ell} = 1\),
    且
    \(u^{-\ell} x^{-\ell} = (u x)^{-\ell} = 1^{-\ell} = 1\),
    故 \(X = x^{-\ell}\).
    则 \((x^\ell)^m = (u^{-\ell})^m
    = X^{-m} = (x^{-\ell})^{-m}
    = x^{(-\ell) (-m)} = x^{\ell m}\).

    (3)
    分类讨论.
    设 \(m \geq 0\).
    则我们已证此情形.

    设 \(m < 0\).
    则 \(-m > 0\).
    因为 \(x \neq 0\), 且 \(y \neq 0\),
    故 \(x y \neq 0\).
    则有 (唯一的) 数 \(W\) 使 \(W (x y) = 1 = (x y) W\).
    注意,
    \((v u) (x y) = v (u x) y = v y = 1\),
    且
    \((x y) (v u) = x (y v) u = x u = 1\),
    故 \(W = v u\).
    则 \((x y)^m = W^{-m} = (v u)^{-m}
    = v^{-m} u^{-m} = y^m x^m = x^m y^m\).

    (1)
    分类讨论.
    设 \(\ell \geq 0\), 且 \(m \geq 0\).
    则我们已证此情形.

    设 \(\ell \geq 0\), \(m < 0\), 且 \(\ell + m \geq 0\).
    则 \(x^{\ell + m}
    = x^{\ell + m} 1^m
    = x^{\ell + m} (x^{-1} x)^m
    = x^{\ell + m} (x^{-1})^m x^m
    = x^{\ell + m} x^{-m} x^m
    = x^{\ell + m + (-m)} x^m
    = x^\ell x^m\).

    设 \(\ell \geq 0\), \(m < 0\), 且 \(\ell + m < 0\).
    则 \(\ell \geq 0\), \(-m > 0\), 且 \(-\ell + (-m) > 0\).
    则 \(x^{\ell + m}
    = u^{-(\ell + m)}
    = u^{-\ell + (-m)}
    = 1^\ell u^{-\ell + (-m)}
    = (x u)^\ell u^{-\ell + (-m)}
    = x^\ell u^\ell u^{-\ell + (-m)}
    = x^\ell u^{\ell + (-\ell) + (-m)}
    = x^\ell u^{-m}
    = x^\ell x^m\).

    设 \(\ell < 0\), 且 \(m \geq 0\).
    则 \(m \geq 0\), 且 \(\ell < 0\).
    则 \(x^{\ell + m}
    = x^{m + \ell}
    = x^m x^\ell
    = x^\ell x^m\).

    设 \(\ell < 0\), 且 \(m < 0\).
    则 \(-\ell > 0\), \(-m > 0\), 且 \(-\ell + (-m) > 0\).
    则 \(x^{\ell + m}
    = u^{-(\ell + m)}
    = u^{-\ell + (-m)}
    = u^{-\ell} u^{-m}
    = x^\ell x^m\).
\end{proof}

\section{结合律、交换律、分配律}

本节, 我想讨论结合律、交换律、分配律.

我们知道, 数的加法适合结合律与交换律;
数的乘法也适合结合律与交换律;
并且, 乘法与加法适合分配律.
具体地, 我们设 \(a\), \(b\), \(c\) 是任何三数.
那么, 加法的结合律就是 \((a + b) + c = a + (b + c)\);
乘法的结合律就是 \((a \cdot b) \cdot c = a \cdot (b \cdot c)\);
加法的交换律就是 \(a + b = b + a\);
乘法的交换律就是 \(a \cdot b = b \cdot a\);
分配律是
\(a \cdot (b + c) = a \cdot b + a \cdot c\)
与
\((a + b) \cdot c = a \cdot c + b \cdot c\),
其中, 形如 \(a \cdot b + c \cdot d\)
的文字应被理解为
\((a \cdot b) + (c \cdot d)\)
(我们通常先算乘法, 再算加法).

% 这些运算律看上去抽象,
% 但我们一直在用它们作计算.

% \begin{example}
%     在小学, 我们学过乘法表.
%     利用乘法表与数的运算律,
%     我们可以作二个数的乘法.
%     比如,
%     \begin{align*}
%         %  & 23 \cdot 57                                    \\
%         23 \cdot 57
%         = {} & 23 \cdot (50 + 7)                              \\
%         = {} & 23 \cdot 50 + 23 \cdot 7                       \\
%         = {} & 23 \cdot (5 \cdot 10) + 23 \cdot 7             \\
%         = {} & (23 \cdot 5) \cdot 10 + 23 \cdot 7             \\
%         = {} & ((20 + 3) \cdot 5) \cdot 10 + (20 + 3) \cdot 7 \\
%         = {} & (20 \cdot 5 + 3 \cdot 5) \cdot 10
%         + (20 \cdot 7 + 3 \cdot 7 )                           \\
%         = {} & (100 + 15) \cdot 10
%         + (140 + 21)                                          \\
%         = {} & 115 \cdot 10 + 161                             \\
%         = {} & 1\,150 + 161                                   \\
%         = {} & (1\,000 + 150) + 161                           \\
%         = {} & 1\,000 + (150 + 161)                           \\
%         = {} & 1\,000 + ((100 + 50) + (100 + 61))             \\
%         = {} & 1\,000 + (((100 + 50) + 100) + 61)             \\
%         = {} & 1\,000 + ((100 + (50 + 100)) + 61)             \\
%         = {} & 1\,000 + ((100 + (100 + 50)) + 61)             \\
%         = {} & 1\,000 + (((100 + 100) + 50) + 61)             \\
%         = {} & 1\,000 + ((100 + 100) + (50 + 61))             \\
%         = {} & 1\,000 + (200 + (50 + (60 + 1)))               \\
%         = {} & 1\,000 + (200 + ((50 + 60) + 1))               \\
%         = {} & 1\,000 + (200 + ((50 + (50 + 10)) + 1))        \\
%         = {} & 1\,000 + (200 + (((50 + 50) + 10) + 1))        \\
%         = {} & 1\,000 + (200 + ((100 + 10) + 1))              \\
%         = {} & 1\,000 + ((200 + (100 + 10)) + 1)              \\
%         = {} & 1\,000 + (((200 + 100) + 10) + 1)              \\
%         = {} & 1\,000 + ((200 + 100) + (10 + 1))              \\
%         = {} & 1\,000 + (300 + (10 + 1))                      \\
%         = {} & 1\,000 + (300 + 11)                            \\
%         = {} & 1\,000 + 311                                   \\
%         = {} & 1\,311.
%     \end{align*}
%     其实, 我还是略了几步;
%     完整地写出计算过程过于复杂了.
% \end{example}

在小学, 我们就知道, 因为加法 (乘法)
适合结合律与交换律,
故当我们求若干个数的和 (积) 时,
我们可随意地交换这些数的次序,
且可以任何方式作加法 (乘法).
比如,
\begin{align*}
    %  & ((23 + 52) + 77) + 48 \\
    ((23 + 52) + 77) + 48
    = {} & (23 + (52 + 77)) + 48 \\
    = {} & (23 + (77 + 52)) + 48 \\
    = {} & ((23 + 77) + 52) + 48 \\
    = {} & (23 + 77) + (52 + 48) \\
    = {} & 100 + (52 + 48)       \\
    = {} & 100 + 100             \\
    = {} & 200.
\end{align*}
不过, 小学教材没有证明此事,
初中教材似乎也没有证明此事,
且高中教材似乎也没有证明此事.

现在, 我接受这个挑战.
不过, 为方便, 我要一些新的概念.

\begin{definition}
    设 \(a\), \(b\) 是二个文字.
    我们叫形如 \((a, b)\) 的文字为\emph{有序对}.

    再设 \(c\), \(d\) 也是二个文字.
    说二个有序对 \((a, b)\), \((c, d)\) 相等,
    就是说, \(a = c\) 且 \(b = d\).
\end{definition}

\begin{definition}
    \emph{集}是具有某个特定性质的对象作成的一个整体.
    我们叫它的对象为\emph{元}.

    无元的集是\emph{空集}.
    自然地, 至少含一个元的集, 是\emph{非空的}.

    若 \(a\) 是集~\(A\) 的元,
    则写 \(a \in A\) 或 \(A \ni a\),
    且说 \(a\) \emph{属于} \(A\)
    或 \(A\) \emph{包含} \(a\).
    若 \(a\) 不是集~\(A\) 的元,
    则写 \(a \notin A\) 或 \(A \not\ni a\),
    且说 \(a\) \emph{不属于} \(A\)
    或 \(A\) \emph{不包含} \(a\).

    一般地, 若集~\(A\) 由元 \(a\), \(b\), \(c\), \(\dots\) 作成,
    我们写
    \begin{align*}
        A = \{ a,b,c,\dots \}.
    \end{align*}
    还有一个记号.
    设集~\(A\) 由具有某个性质 \(p\) 的对象作成.
    我们写
    \begin{align*}
        A = \{ x \mid \text{\(x\) 具有性质 \(p\)} \}.
    \end{align*}
\end{definition}

\begin{example}
    当我们视所有的整数为一个整体时,
    这个整体, 就是\emph{整数集}.
    习惯地, 我们表它以 \(\mathbb{Z}\).

    我们常记由全体非负整数 (自然数) 作成的集为 \(\mathbb{N}\).
    那么, 我们可写
    \begin{align*}
        \mathbb{N} = \{ 0, 1, 2, \dots \}.
    \end{align*}
    不难看出, \(-1 \in \mathbb{Z}\),
    但 \(-1 \notin \mathbb{N}\).

    我们可写
    \begin{align*}
        \mathbb{Z} = \{ 0, 1, -1, 2, -2, \dots \}.
    \end{align*}
    我们也可写
    \begin{align*}
        \mathbb{Z} =
        \{ x \mid \text{\(x \in \mathbb{N}\)
            或 \(-x \in \mathbb{N}\)} \}.
    \end{align*}
\end{example}

\begin{definition}
    设 \(S\), \(T\) 是二个非空的集.
    定义
    \begin{align*}
        S \times T
        = \{ (s, t) \mid \text{\(s \in S\), \(t \in T\)} \}.
    \end{align*}
\end{definition}

\begin{example}
    设 \(A = \{ 1, 2, 3\}\),
    \(B = \{4, 5\}\).
    那么,
    \begin{align*}
        A \times B
        = \{ (1,4),(1,5),(2,4),(2,5),(3,4),(3,5) \}.
    \end{align*}
    不过,
    \begin{align*}
        B \times A
        = \{ (4,1),(4,2),(4,3),(5,1),(5,2),(5,3) \}.
    \end{align*}
    可以看到, 虽然 \(A \times B\) 与 \(B \times A\)
    的元的数目是相同的,
    但二者的元是不一样的.
\end{example}

抽象地, \(a + b\) 的 \(+\),
其实是一个对应法则:
\(+\) 变一个有序对 \((a, b)\)
为某一个唯一确定的数 \(s\),
其可被表示为 \(a + b\).
类似地, \(\cdot\) 变一个有序对 \((a, b)\)
为某一个唯一确定的数 \(p\),
其可被表示为 \(a \cdot b\),
且也可被特别地表示为 \(ab\).

\begin{definition}
    设 \(S\) 是非空的集.
    设对应法则~\(\circ\) 适合:
    对 \(S \times S\) 的任何一个有序对 \((a, b)\),
    必存在 \(S\) 里的唯一的一个元 \(r\),
    使在对应法则~\(\circ\) 下,
    \((a, b)\) 跟 \(r\) 对应.
    (也就是:
    (a)
    对 \(S\) 的任何二元 \(a\), \(b\)
    (不必互不相同),
    存在 \(S\) 的元 \(r\),
    使在对应法则~\(\circ\) 下,
    \((a, b)\) 跟 \(r\) 对应;
    (b)
    若在对应法则~\(\circ\) 下,
    \((a, b)\) 跟 \(r\) 对应,
    且 \((a, b)\) 跟 \(t\) 对应,
    则 \(r = t\).)
    那么, 我们说, \(\circ\) 是 \(S\) 的%
    一个\emph{二元运算}.

    设在对应法则~\(\circ\) 下,
    \((a, b)\) 跟 \(r\) 对应.
    我们表此事以 \(a \circ b = r\).
\end{definition}

\begin{example}
    加法与乘法都是 \(\mathbb{N}\)~的二元运算:
    二个给定的非负整数 \(a\), \(b\)
    的和 (或积) 是被唯一确定的非负整数
    \(a + b\)
    (或 \(ab\)).
    不过, 减法不是:
    二个非负整数的差不一定是非负整数.

    不过, 减法是 \(\mathbb{Z}\)~的二元运算.
    当然, 加法与乘法也是.
\end{example}

我们考虑运算律.

我们先看结合律.

设 \(S\) 为非空的集.
设 \(\circ\) 是 \(S\) 的二元运算.
文字 \(a \circ b \circ c\) 是否有意义?
显然, 我们并没有定义它的含义:
二元运算每次只对二个元作运算.
不过, 我们总可以先挑二个元作运算,
然后再作一次运算.
比如, 先施 \(\circ\) 于 \(a\), \(b\),
可得 \((a \circ b) \circ c\);
先施 \(\circ\) 于 \(b\), \(c\),
可得 \(a \circ (b \circ c)\).
二者不一定相同,
因为二元运算是相当自由的.

\begin{example}
    \(
    (11 - 5) - 2 \neq 11 - (5 - 2).
    \)
\end{example}

不过, 当然, 有 \((a \circ b) \circ c\)
总等于 \(a \circ (b \circ c)\)
的情形.

\begin{definition}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    若对 \(S\) 的任何三元 \(a\), \(b\), \(c\)
    (不一定是互不相同的, 下同),
    必有
    \begin{align*}
        (a \circ b) \circ c = a \circ (b \circ c),
    \end{align*}
    我们说, \(\circ\) 适合\emph{结合律}.
\end{definition}

通俗地, 结合律说,
若非空的集 \(S\) 的二元运算 \(\circ\) 适合结合律,
且 \(a\), \(b\), \(c\) 为 \(S\) 的任何 \(3\)~元,
则无论如何加括号
(但不改元的前后次序),
结果都是相等的.

我们看结合律有何用.

设 \(S\) 是非空的集.
设 \(\circ\) 是 \(S\) 的二元运算.
设 \(\circ\) 适合结合律.
设 \(a\), \(b\), \(c\), \(d\) 是 \(S\) 的 \(4\)~个元.
考虑文字 \(a \circ b \circ c \circ d\).
显然, 它并没有含义
(二元运算每次只对二个元作运算).
不过, 我们总可以二个二个地作运算.
% 我们总可以选二个元 ``结合'',
% 然后, 连同上步的结果, 再选二个元结合,
% 直到剩一个元为止.
具体地, 我们有如下 \(5\)~个结合 (加括号) 方式:
\begin{align*}
     & r_{4,1} = ((a \circ b) \circ c) \circ d, \\
     & r_{4,2} = (a \circ (b \circ c)) \circ d, \\
     & r_{4,3} = a \circ ((b \circ c) \circ d), \\
     & r_{4,4} = a \circ (b \circ (c \circ d)), \\
     & r_{4,5} = (a \circ b) \circ (c \circ d).
\end{align*}
不难用结合律验证,
\(r_{4,2}\), \(r_{4,3}\), \(r_{4,4}\), \(r_{4,5}\)
都等于 \(r_{4,1}\):
\begingroup
\reqnomode
\begin{align*}
    r_{4,1}
    = {} & ((a \circ b) \circ c) \circ d
    \\
    = {} & (a \circ (b \circ c)) \circ d
    \tag*{(\(r_{4,2}\))}                  \\
    = {} & a \circ ((b \circ c) \circ d)
    \tag*{(\(r_{4,3}\))}                  \\
    = {} & a \circ (b \circ (c \circ d))
    \tag*{(\(r_{4,4}\))}                  \\
    = {} & (a \circ b) \circ (c \circ d).
    \tag*{(\(r_{4,5}\))}
\end{align*}
\endgroup
所以, 通俗地,
若非空的集 \(S\) 的二元运算 \(\circ\) 适合结合律,
且 \(a\), \(b\), \(c\), \(d\) 为 \(S\) 的任何 \(4\)~元,
则无论如何加括号
(但不改元的前后次序),
结果都是相等的.

一般地, 我们有

\begin{theorem}
    设非空的集 \(S\) 的二元运算 \(\circ\) 适合结合律,
    且 \(a_1\), \(a_2\), \(\dots\), \(a_n\) 为
    \(S\) 的任何 \(n\)~元.
    则无论如何加括号
    (但不改元的前后次序),
    结果都是相等的.
\end{theorem}

为方便,
我引入一个小的记号.
我们证明此事后, 就不再用这个记号.

\begin{definition}
    设 \(\circ\) 是 \(S\) 的二元运算.
    设 \(a_1\), \(a_2\), \(\dots\), \(a_n\) 是
    \(S\)~的 \(n\)~个元.
    定义
    \begin{align*}
        [a_1, a_2, \dots, a_n]
        =
        \begin{cases}
            a_1,
             & n = 1;    \\
            a_1 \circ a_2,
             & n = 2;    \\
            [a_1, a_2, \dots, a_{n-1}] \circ a_n,
             & n \geq 3.
        \end{cases}
    \end{align*}
    由此可见, \([a_1, a_2, \dots, a_n]\)
    就是从前向后地, 二个二个地%
    施 \(\circ\) 于
    \(a_1\), \(a_2\), \(\dots\), \(a_n\)
    得到的结果.
\end{definition}

为方便, 我们说,
施 \(\circ\) 于 \(S\) 的一个元 \(a\) 的结果%
就是 \(a\) 自己.

\begin{proof}
    注意, 有限多个元, 只有有限多个加括号的方式.
    设 \(a_1\), \(a_2\), \(\dots\), \(a_n\)
    有 \(s_n\)~个加括号的方式
    (比如, \(s_1 = s_2 = 1\),
    \(s_3 = 2\), \(s_4 = 5\)).
    设以第~\(i\)~个加括号的方式算出的结果为 \(r_{n,i}\).
    我们证明,
    它们都等于
    \([a_1, a_2, \dots, a_n]\)
    (注意, 这也是一个加括号的方式,
    故它必跟 \(r_{n,1}\), \(r_{n,2}\), \(\dots\),
    \(r_{n,s_n}\) 中的一个%
    有相同的计算式).
    具体地, 设命题 \(P(n)\) 为
    \begin{quotation}
        对 \(S\) 的任何 \(n\)~元
        \(a_1\), \(a_2\), \(\dots\), \(a_n\),
        无论如何加括号
        (但不改元的前后次序),
        施 \(\circ\) 于此 \(n\)~元的结果都等于
        \([a_1, a_2, \dots, a_n]\).
    \end{quotation}
    我们再作一个辅助命题 \(Q(n)\):
    \begin{quotation}
        对任何不超过 \(n\) 的正整数 \(i\),
        \(P(i)\) 是对的.
    \end{quotation}
    我们用数学归纳法证明,
    对每个整数 \(n \geq 3\),
    \(Q(n)\) 是对的.

    显然, \(Q(3)\) 是对的.

    现在, 我们假定, \(Q(m-1)\) 是对的.
    我们要证, \(Q(m)\) 也是对的.

    因为 \(Q(m-1)\) 是对的,
    故 \(P(1)\), \(P(2)\), \(\dots\), \(P(m-1)\) 都是对的.
    所以, 若我们能由此证明 \(P(m)\) 是对的,
    则 \(Q(m)\) 是对的.

    任取 \(S\) 的 \(m\)~元
    \(a_1\), \(a_2\), \(\dots\), \(a_m\).
    任取一个 \(r_{m,i}\).
    注意, 无论如何加括号作计算,
    最后的那一步总是二个元的计算
    (可回想 \(4\)~个元时的情形).
    我们设 \(r_{m,i} = b_1 \circ b_2\),
    其中, \(b_1\) 是结合 \(a_1\), \(a_2\), \(\dots\), \(a_m\)
    的前 \(k\) 个元的结果,
    且 \(b_2\) 是结合 \(a_1\), \(a_2\), \(\dots\), \(a_m\)
    的后 \(m-k\) 个元的结果.
    注意, \(k\), \(m-k\) 都低于 \(m\),
    且都不低于 \(1\)
    (因为 \(k \geq 1\)),
    故, 由假定,
    \begin{align*}
        b_1 = [a_1, a_2, \dots, a_k],
        \quad
        b_2 = [a_{k+1}, \dots, a_m].
    \end{align*}
    若 \(m - k = 1\), 那么 \(b_2\) 就是 \(a_m\) 自己.
    故
    \begin{align*}
        r_{m,i}
            = [a_1, a_2, \dots, a_{m-1}] \circ a_m
        = [a_1, a_2, \dots, a_m].
    \end{align*}
    若 \(m - k > 1\), 则
    \begin{align*}
        r_{m,i}
        = {} &
        b_1 \circ b_2
        \\
        = {} &
        [a_1, a_2, \dots, a_k] \circ
        [a_{k+1}, \dots, a_{m-1}, a_m]
        \\
        = {} &
        [a_1, a_2, \dots, a_k] \circ
        ([a_{k+1}, \dots, a_{m-1}] \circ a_m)
        \\
        = {} &
        ([a_1, a_2, \dots, a_k] \circ
        [a_{k+1}, \dots, a_{m-1}]) \circ a_m
        \\
        = {} &
        [a_1, a_2, \dots, a_k, a_{k+1}, \dots, a_{m-1}]
        \circ a_m
        \\
        = {} &
        [a_1, a_2, \dots, a_m].
    \end{align*}
    所以, \(Q(m)\) 是对的.

    由数学归纳法, \(Q(n)\) 对%
    任何整数~\(n \geq 3\) 都是成立的.
    进而, \(P(n)\) 对任何正整数~\(n\) 是成立的.
\end{proof}

设 \(\circ\) 是非空的集 \(S\) 的适合结合律的二元运算.
设 \(a_1\), \(a_2\), \(\dots\), \(a_n\) 为 \(S\) 的任何 \(n\)~元.
我们简单地写
\begin{align*}
    (((a_1 \circ a_2) \circ \dots) \circ a_{n-1}) \circ a_n,
\end{align*}
或任何加括号的方式, 为
\begin{align*}
    a_1 \circ a_2 \circ \dots \circ a_{n-1} \circ a_n.
\end{align*}

然后, 我们看交换律.

设 \(S\) 为非空的集.
设 \(\circ\) 是 \(S\) 的二元运算.
设 \(a\), \(b \in S\).
自然地, \(a \circ b\) 与 \(b \circ a\) 都有意义.
因为二元运算是相当自由的,
故二者不一定相等.

\begin{example}
    \(
    7 - 3 \neq 3 - 7.
    \)
\end{example}

不过, 当然, 有 \(a \circ b\)
总等于 \(b \circ a\)
的情形.

\begin{definition}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    若对 \(S\) 的任何二元 \(a\), \(b\),
    必有
    \begin{align*}
        a \circ b = b \circ a,
    \end{align*}
    我们说, \(\circ\) 适合\emph{交换律}.
\end{definition}

现在, 我们证明前面提的重要事实:
当我们求若干个数的和 (积) 时,
我们可随意地交换这些数的次序,
且可以任何方式作加法 (乘法).

\begin{theorem}
    设非空的集 \(S\) 的二元运算 \(\circ\) 适合%
    结合律与交换律,
    且 \(a_1\), \(a_2\), \(\dots\), \(a_n\)
    为 \(S\) 的任何 \(n\)~元.
    则无论如何加括号与交换元的前后次序,
    结果都是相等的.
\end{theorem}

\begin{proof}
    设命题 \(P(n)\) 为
    \begin{quotation}
        对 \(S\) 的任何 \(n\)~元
        \(a_1\), \(a_2\), \(\dots\), \(a_n\),
        无论如何加括号与交换元的前后次序,
        施 \(\circ\) 于此 \(n\)~元的结果都等于
        \(a_1 \circ a_2 \circ \dots \circ a_n\).
    \end{quotation}
    我们用数学归纳法证明,
    对每个正整数 \(n\), \(P(n)\) 是对的.

    \(P(1)\) 是对的.

    \(P(2)\) 是对的, 因为交换律.

    现在, 我们假定, \(P(m-1)\) 是对的.
    我们要证, \(P(m)\) 也是对的.

    任取 \(S\) 的 \(m\)~元
    \(a_1\), \(a_2\), \(\dots\), \(a_m\).
    设 \(i_1\), \(i_2\), \(\dots\), \(i_m\)
    是不超过 \(m\) 的正整数,
    且互不相同.
    % 因为结合律, 故, 无论如何加括号,
    % 施 \(\circ\) 于
    % \(a_{i_1}\), \(a_{i_2}\), \(\dots\), \(a_{i_m}\)
    % 的结果都等于
    % \(a_{i_1} \circ a_{i_2} \circ \dots \circ a_{i_m}\).
    % 我们证它等于
    % \(a_1 \circ a_2 \circ \dots \circ a_m\)
    % 即可.

    若 \(i_m = m\),
    则 \(i_1\), \(i_2\), \(\dots\), \(i_{m-1}\)
    是不超过 \(m-1\) 的正整数,
    且互不相同.
    故
    \begin{align*}
             & a_{i_1} \circ a_{i_2} \circ
        \dots \circ a_{i_{m-1}} \circ a_{i_m}               \\
        = {} &
        (a_{i_1} \circ a_{i_2} \circ
        \dots \circ a_{i_{m-1}}) \circ a_m                  \\
        = {} &
        (a_1 \circ a_2 \circ \dots \circ a_{m-1}) \circ a_m \\
        = {} &
        a_1 \circ a_2 \circ \dots \circ a_{m-1} \circ a_m.
    \end{align*}

    若 \(i_m \neq m\),
    我们设 \(i_j = m\).
    则
    (若 \(i_1 = m\),
    则 \(a_{i_1} \circ \dots \circ a_{i_{j-1}}\)
    不出现)
    \begin{align*}
             & a_{i_1} \circ a_{i_2} \circ
        \dots \circ a_{i_m}                                 \\
        = {} & (a_{i_1} \circ \dots \circ a_{i_{j-1}})
        \circ (a_{i_j}
        \circ (a_{i_{j+1}} \circ \dots \circ a_{i_m}))      \\
        = {} & (a_{i_1} \circ \dots \circ a_{i_{j-1}})
        \circ ((a_{i_{j+1}} \circ \dots \circ a_{i_m})
        \circ a_{i_j})                                      \\
        = {} & ((a_{i_1} \circ \dots \circ a_{i_{j-1}})
        \circ (a_{i_{j+1}} \circ \dots \circ a_{i_m}))
        \circ a_m                                           \\
        = {} &
        (a_1 \circ a_2 \circ \dots \circ a_{m-1}) \circ a_m \\
        = {} &
        a_1 \circ a_2 \circ \dots \circ a_{m-1} \circ a_m.
    \end{align*}

    所以, \(P(m)\) 是对的.
    由数学归纳法, 待证命题成立.
\end{proof}

注意, 只有交换律而没有结合律的二元运算%
是没有这个好性质的.

\begin{example}
    定义 \(\mathbb{Z}\) 上的二元运算
    \(a \circ b = ab - (a + b)\).
    不难验证, \(\circ\) 适合交换律.
    我们取 \(a\), \(b\), \(c\), \(d\)
    为 \(2\), \(3\), \(5\), \(7\).
    则
    \begin{align*}
         & (2 \circ 3) \circ (5 \circ 7) = 1 \circ 23 = -1; \\
         & (2 \circ 5) \circ (3 \circ 7) = 3 \circ 11 = 19.
    \end{align*}
    不难发现, \(\circ\) 不适合结合律:
    \begin{align*}
         & (1 \circ 0) \circ 0 = -1 \circ 0 = 1; \\
         & 1 \circ (0 \circ 0) = 1 \circ 0 = -1.
    \end{align*}
\end{example}

最后, 我们看分配律.

\begin{definition}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    设 \(\oplus\) 也是 \(S\) 的二元运算.

    若对 \(S\) 的任何三元 \(a\), \(b\), \(c\),
    必有
    \begin{align*}
        a \circ (b \oplus c)
        = (a \circ b) \oplus (a \circ c),
    \end{align*}
    我们说, \(\circ\) 与 \(\oplus\) 适合\emph{左分配律}.

    若对 \(S\) 的任何三元 \(a\), \(b\), \(c\),
    必有
    \begin{align*}
        (a \oplus b) \circ c
        = (a \circ c) \oplus (b \circ c),
    \end{align*}
    我们说, \(\circ\) 与 \(\oplus\) 适合\emph{右分配律}.

    若 \(\circ\) 与 \(\oplus\)
    既适合左分配律, 也适合右分配律,
    我们说,
    \(\circ\) 与 \(\oplus\) 适合\emph{分配律}.
\end{definition}

若 \(\oplus\) 适合结合律,
我们可得如下三个结果.

\begin{theorem}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    设 \(\oplus\) 是 \(S\) 的二元运算,
    且适合结合律.
    再设 \(\circ\) 与 \(\oplus\) 适合左分配律.
    则对 \(S\) 的任何 \(n + 1\)~元
    \(b\), \(a_1\), \(a_2\) \(\dots\), \(a_n\),
    \begin{align*}
        b \circ (a_1 \oplus a_2 \oplus \dots \oplus a_n)
        =
        (b \circ a_1) \oplus (b \circ a_2) \oplus
        \dots \oplus (b \circ a_n).
    \end{align*}
\end{theorem}

\begin{proof}
    设命题 \(P(n)\) 为
    \begin{quotation}
        对 \(S\) 的任何 \(n + 1\)~元
        \(b\), \(a_1\), \(a_2\), \(\dots\), \(a_n\),
        \begin{align*}
            b \circ (a_1 \oplus a_2 \oplus \dots \oplus a_n)
            =
            (b \circ a_1) \oplus (b \circ a_2) \oplus
            \dots     \oplus (b \circ a_n).
        \end{align*}
    \end{quotation}
    我们用数学归纳法证明,
    对每个正整数 \(n\), \(P(n)\) 是对的.

    \(P(1)\) 是对的 (显然).

    \(P(2)\) 是对的, 因为左分配律.

    现在, 我们假定, \(P(m-1)\) 是对的.
    我们要证, \(P(m)\) 也是对的.

    任取 \(S\) 的 \(m + 1\)~元
    \(b\), \(a_1\), \(a_2\), \(\dots\), \(a_m\).
    则
    \begin{align*}
             &
        b \circ (a_1 \oplus a_2 \oplus \dots \oplus a_m)
        \\
        = {} &
        b \circ ((a_1 \oplus a_2 \oplus \dots \oplus a_{m-1})
        \oplus a_m)
        \\
        = {} &
        (b \circ (a_1 \oplus a_2 \oplus \dots \oplus a_{m-1}))
        \oplus (b \circ a_m)
        \\
        = {} &
        ((b \circ a_1) \oplus (b \circ a_2) \oplus
        \dots \oplus (b \circ a_{m-1}))
        \oplus (b \circ a_m)
        \\
        = {} &
        (b \circ a_1) \oplus (b \circ a_2) \oplus
        \dots \oplus (b \circ a_m).
    \end{align*}
    所以, \(P(m)\) 是对的.
    由数学归纳法, 待证命题成立.
\end{proof}

您可用完全类似的方法, 证明如下二个事实.
我就不证它们了.

\begin{theorem}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    设 \(\oplus\) 是 \(S\) 的二元运算,
    且适合结合律.
    再设 \(\circ\) 与 \(\oplus\) 适合右分配律.
    则对 \(S\) 的任何 \(n + 1\)~元
    \(b\), \(a_1\), \(a_2\) \(\dots\), \(a_n\),
    \begin{align*}
        (a_1 \oplus a_2 \oplus \dots \oplus a_n) \circ b
        =
        (a_1 \circ b) \oplus (a_2 \circ b) \oplus
        \dots \oplus (a_n \circ b).
    \end{align*}
\end{theorem}

\begin{theorem}
    设 \(S\) 是非空的集.
    设 \(\circ\) 是 \(S\) 的二元运算.
    设 \(\oplus\) 是 \(S\) 的二元运算,
    且适合结合律.
    再设 \(\circ\) 与 \(\oplus\) 适合分配律.
    则对 \(S\) 的任何 \(n + 1\)~元
    \(b\), \(a_1\), \(a_2\) \(\dots\), \(a_n\),
    \begin{align*}
         &
        b \circ (a_1 \oplus a_2 \oplus \dots \oplus a_n)
        =
        (b \circ a_1) \oplus (b \circ a_2) \oplus
        \dots \oplus (b \circ a_n),
        \\
         &
        (a_1 \oplus a_2 \oplus \dots \oplus a_n) \circ b
        =
        (a_1 \circ b) \oplus (a_2 \circ b) \oplus
        \dots \oplus (a_n \circ b).
    \end{align*}
\end{theorem}

\end{document}

This material is about:
\begin{itemize}
    \item the summation symbol: Sigma
    \item the product symbol: Pi
    \item mathematical induction
    \item associativity, commutativity, and distributivity
\end{itemize}
One should know the summation symbol
and mathematical induction
before learning chapter 1.
